#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣2466. 统计构造好字符串的方案数
// 【难度】中等
// 【提交】2025.10.23 https://leetcode.cn/problems/count-ways-to-build-good-strings/submissions/673029080/
// 【标签】动态规划
class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1'000'000'007;
        int ans = 0;
        vector<int> f(high + 1);
        f[0] = 1;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) f[i] = f[i - zero];
            if (i >= one)  f[i] = (f[i] + f[i - one]) % MOD;
            if (i >= low)  ans = (ans + f[i]) % MOD;
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定整数low, high, zero, one，使用0和1构造字符串，每次可以添加zero个0或one个1。
 * 统计所有长度在[low, high]范围内且满足条件的字符串数目。
 * 模型：动态规划，计算构造特定长度字符串的方案数。
 * 
 * 二、标准解法状态设计
 * 设f[i]表示构造长度为i的字符串的方案数。
 * 状态转移方程：f[i] = f[i-zero] + f[i-one]
 * 初始状态：f[0] = 1（空字符串）
 * 在计算过程中累加长度在[low, high]范围内的方案数
 * 
 * 三、你的实现思路
 * 使用动态规划方法，通过f数组记录构造每个长度字符串的方案数。
 * 在循环中同时计算方案数和累加结果，减少一次额外循环。
 * 
 * 四、复杂度
 * 时间：O(high)，需要计算从1到high的每个长度。
 * 空间：O(high)，需要f数组存储中间结果。
 * 
 * 五、优缺点分析
 * 优点：
 *   - 算法高效，只需一次循环；
 *   - 在计算过程中直接累加结果，减少额外循环；
 *   - 使用模运算防止整数溢出。
 * 缺点：
 *   - 空间复杂度为O(high)，对于较大的high值可能占用较多内存；
 *   - 无法直接获取每种长度的具体方案。
 * 
 * 六、改进建议
 * 1. 可以优化空间复杂度到O(max(zero, one))，使用滚动数组；
 * 2. 可以添加输入验证，确保参数有效性；
 * 3. 对于极大的high值，可以考虑数学优化方法。
 * 
 * 七、一句话总结
 * 动态规划是解决字符串构造方案数问题的标准方法，你的实现高效且优化良好。
 */